import java.util.*;

public class Test {
    /*
    题目1：三数之和
     */

    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        // 使用双指针来求解

        int n = num.length;

        Arrays.sort(num);

        for (int i = 0; i < n - 2;) {
            int tg = -num[i];
            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                int sum = num[left] + num[right];

                if (tg > sum) {
                    left++;
                } else if (tg < sum) {
                    right--;
                } else {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(num[i]);
                    list.add(num[left]);
                    list.add(num[right]);
                    lists.add(list);
                    left++;
                    right--;
                    while (left < right && num[left] == num[left - 1]) {
                        left++;
                    }

                    while (left < right && num[right] == num[right + 1]) {
                        right--;
                    }
                }
            }

            i++;
            while (i < n - 2 && num[i] == num[i - 1]) {
                i++;
            }
        }
        return lists;
    }

    /*
    题目 2：打家劫舍Ⅰ
     */
    // dp[i] 表示 到 i 位置时，偷到的最多的钱
    // 进一步细化成
    // f[i] : 到 i 位置，必偷的最多钱数
    // g[i]：到 i 位置，不偷的最多钱数
    public int robb (int[] nums) {
        int n = nums.length;
        // 创建 dp 表
        int[] f = new int[n];
        int[] g = new int[n];

        // 初始化 dp 表
        f[0] = nums[0];
        g[0] = 0;

        // 填表
        for(int i = 1; i < n; i++){
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(f[i - 1], g[i - 1]); // 前一个可偷，可不偷
        }

        // 返回值

        return Math.max(f[n - 1], g[n - 1]);
    }

    /*
    题目3： 打家劫舍Ⅱ
     */
    private int rob1(int[] nums, int start, int end){
        int n = nums.length;

        int[] f = new int[n];
        int[] g = new int[n];

        f[start] = nums[start];
        f[start] = nums[start];
        //g[start] = 0; 这一条真的不用再写啦！！



        for(int i = start + 1 ; i < end; i++){
            f[i] = g[i - 1] + nums[i];
            g[i] = Math.max(g[i - 1], f[i - 1]);
        }

        return Math.max(f[end - 1], g[end - 1]);

    }

    public int rob (int[] nums) {
        int n = nums.length;
        // 把问题转换成 打家劫舍 Ⅰ 即可
        return Math.max(rob1(nums, 0, n - 1), rob1(nums, 1, n));
    }

    /*
    题目 4：买卖股票的最好时机Ⅰ
     */
    public int maxProfit (int[] p) {
        int n = p.length;

        int[][] dp = new int[n][2];

        dp[0][0] = -p[0];
        // 第一天没办法卖出，所以 dp[0][1] = 0，无需写出来

        for(int i = 1; i < n; i++){
            // 总共只能 买入 卖出 一次！
            dp[i][0] = Math.max(dp[i - 1][0], - p[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + p[i]);
        }

        return dp[n - 1][1];
    }

    /*
    题目 5：买卖股票的最好时机Ⅲ
     */
    public int maxProfit1 (int[] p) {
        int n = p.length;

        // f[i][j] 表示 第 i 天， 进行 j 次交易之后，处于 买入 状态的最大收益
        int[][] f = new int[n][3];

        // g[i][j] 表示 第 i 天， 进行 j 次交易之后，处于 可交易 状态的最大收益
        int[][] g = new int[n][3];

        int INF = -0x3f3f3f3f;

        for(int i = 0; i < 3; i++){
            g[0][i] = INF;
            f[0][i] = INF;
        }

        f[0][0] = -p[0];
        g[0][0] = 0;

        for(int i = 1; i < n; i++){
            for(int j = 0; j < 3; j++){
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - p[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1  >= 0){
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + p[i]);
                }
            }
        }

        int ret = 0;
        for(int i = 0; i < 3; i++){
            ret = Math.max(ret, g[n - 1][i]);
        }

        return ret;
    }

    /*
    题目 6：连续子数组的最大和
     */
    public int FindGreatestSumOfSubArray (int[] array) {
        int n = array.length;

        int[] sum = new int[n];
        sum[0] = array[0];

        int max  = -250;


        for(int i = 1; i < n; i++){
            sum[i] = Math.max(array[i], sum[i - 1] + array[i]);
            max = Math.max(max, sum[i]) ;
        }

        return max == -250? array[0]:max;
    }


    /*
    题目 7：合并两个有序数组
     */
    public void merge(int A[], int m, int B[], int n) {

        int k = m + n - 1;
        int i = m - 1;
        int j = n - 1;

        while(k >= 0 && i >= 0 && j >= 0){
            if(A[i] > B[j]){
                A[k--] = A[i--];
            }else{
                A[k--] = B[j--];
            }
        }

        while(j >= 0){
            A[k--] = B[j--];
        }
    }

    /*
    题目 8：移动 零
     */
    public void moveZeroes(int[] nums) {
        int n = nums.length;

        for(int cur = 0, dest = -1; cur < n; cur++){
            if(nums[cur] != 0){
                dest++;
                int temp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = temp;
            } // 太巧妙了！

        }
    }

    /*
    题目 9：复写 0
     */
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int cur = 0;
        int dest = -1;

        while(cur < n){
            if(arr[cur] != 0) dest += 1;
            else dest += 2;
            if(dest >= n - 1){
                break;
            }
            cur++;
        }

        // 能让 dest 跑到 n 的 cur 一定是 0！！
        // 因为不是走一步就是走两步，只有最后走两步的情况才可能走到 n
        if(dest == n){
            arr[n - 1] = 0;
            dest -= 2;
            cur--;
        }

        // 复写 0 操作
        while(cur >= 0){
            if(arr[cur] != 0){
                arr[dest--] = arr[cur--];
            }else{
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }

    /*
    题目 10：快乐数
     */
    private int decimal(int x){
        int sum = 0;
        while(x > 0){
            int t = x % 10;
            sum += t * t;
            x /= 10;
        }
        return sum;
    }

    // 这道题有个结论吧
    // 任何一个数 十进制位上每一位的平方和 最后都能成为一个循环
    public boolean isHappy(int n) {
        // 借鉴了链表是否有环的解法，快慢指针！
        int slow = n;
        int fast = decimal(n);

        while(fast != slow){
            fast = decimal(decimal(fast));
            slow = decimal(slow);

        }

        if(fast == 1){
            return true;
        }else{
            return false;
        }
    }

    /*
    题目 11：盛最多水的容器
     */
    public int maxArea (int[] h) {
        int n = h.length;
        int left = 0;
        int right = n - 1;
        int maxSum = 0;

        // 挪动长的边，固定短的一边为什么不行？
        // 不管下一条边长度如何，都一定会使 容积变小！
        while(left < right){
            int ret = Math.min(h[left], h[right]) * (right - left);
            maxSum = Math.max(ret, maxSum);

            if(h[left] < h[right]){
                left++;
            }else{
                right--;
            }
        }
        return maxSum;
    }

    

}
